package com.cqs.leetcode.offerII;

/**
 * xw
 * 2022/10/3
 */
public class OfferII009 {

    public boolean isMatch(String s, String p) {
        boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
        dp[0][0] = true;
        for (int i = 1; i <= p.length(); i++) {
            char cp = p.charAt(i - 1);
            for (int j = 1; j <= s.length(); j++) {
                char cs = s.charAt(j - 1);
                boolean b1 = dp[i - 1][j - 1] && (cp == cs || cp == '*' || cp == '?');
                boolean b2 = dp[i - 1][j] && i > 1 && p.charAt(i - 2) == '*';
                boolean b3 = dp[i][j - 1] && cp == '*';
                dp[i][j] = b1 || b2 || b3;
            }
        }
        return dp[p.length()][s.length()];
    }

    public int numSubarrayProductLessThanK(int[] nums, int k) {
        int target = 1, left = 0, result = 0;
        //计算右边界是right的个数
        for (int right = 0; right < nums.length; right++) {
            target *= nums[right];
            while (left <= right && target >= k) {
                target /= nums[left++];
            }
            result += right - left + 1;
        }
        return result;
    }

    public int numSubarrayProductLessThanK0(int[] nums, int k) {
        int cnt = 0;
        for (int i = 0; i < nums.length; i++) {
            long target = 1;
            for (int j = i; j < nums.length; j++) {
                target *= nums[j];
                if (target >= k) {
                    break;
                }
                ++cnt;
            }
        }
        return cnt;
    }
}
